package com.techyuan.algorithm.sorts;


/**
 * 插入排序 时间复杂度:Θ(n的2次方)
 * Created by tianjuntao on 2016/9/4.
 */
public class InsertionSort implements ISort {
    public int[] sort(int[] sortingArr) {
        sort(sortingArr, 0, sortingArr.length - 1);
        return sortingArr;
    }

    public void sort(int[] sortingArr, int start, int end) {
        if (start < end) {
            for (int j = start + 1; j <= end; j++) {
                Integer key = sortingArr[j];
                int i = j - 1;
                while (i >= start && sortingArr[i] > key) {
                    sortingArr[i + 1] = sortingArr[i];
                    i = i - 1;
                }
                sortingArr[i + 1] = key;
            }
        }
    }
}
